#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> grayCode(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
		if(n<=0)
			return vector<int>(1,0);

		vector<int> result;		
		solve(result,n);
		return result;
    }

private:
	void solve(vector<int>& result,int n)
	{
		if(n == 1)
		{
			result.push_back(0);
			result.push_back(1);
			return;
		}
		solve(result,n-1);
		size_t lastN = result.size();
		result.resize(2*lastN,0);
		size_t curIdx = lastN;
		int code = 1<<(n-1);
		for(;curIdx<result.size();curIdx++)
			result[curIdx] = code | result[2*lastN-1-curIdx];
	}
};
#endif